
enum Colour{
    BLACK,
    RED
};

template<class K,class V>
struct BRTreeNode
{
    BRTreeNode<K,V> *_left;
    BRTreeNode<K,V> *_right;
    BRTreeNode<K,V> *_parent;
    pair<K,V> _val;
    Colour _col;

    //构造函数
    BRTreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_val(kv)
    ,_col(RED)
    {}
};

template<class K,class V>
class BRT
{
    typedef BRTreeNode<K,V> Node;

    void RotateR(Node * parent)//右单旋
    {
        Node * parentL=parent->_left;
        Node * parentLR=parentL->_right;
        Node * pparent=parent->_parent;

        parent->_left=parentLR;
        parentL->_right=parent;

        //更改父亲节点
        if(parentLR)
        {
            parentLR->_parent=parent;
        }
        parent->_parent=parentL;

        if(pparent== nullptr)
        {
            _root=parentL;
            parentL->_parent= nullptr;
        }
        else
        {
            if(pparent->_left==parent)
                pparent->_left=parentL;
            else if(pparent->_right==parent)
                pparent->_right=parentL;

            parentL->_parent=pparent;
        }


    }
    void RotateL(Node * parent)//左单旋
    {
        Node  * parentR=parent->_right;
        Node  * parentRL=parentR->_left;
        Node  * pparent=parent->_parent;

        parent->_right=parentRL;
        parentR->_left=parent;

        if(parentRL)
        {
            parentRL->_parent=parent;
        }
        parent->_parent=parentR;

        if(pparent== nullptr)
        {
            _root=parentR;
            parentR->_parent= nullptr;
        }
        else
        {
            if(pparent->_left==parent)
                pparent->_left=parentR;
            else if(pparent->_right==parent)
                pparent->_right=parentR;

            parentR->_parent=pparent;
        }

    }

    bool Continuation(Node * cur)
    {
        if(cur ==nullptr)
        {
            return true;
        }

        if(cur->_col==RED &&cur->_parent->_col==RED)
        {
            return false;
        }
        return Continuation(cur->_left) && Continuation(cur->_right);
    }

    bool CheckBlackNumber(Node *cur,int count,int&b_c)
    {
        if(cur==nullptr)
        {
            if(count !=b_c)
            {
                return false;
            }
            return true;
        }

        if(cur->_col==BLACK)
        {
            count++;
        }
        return CheckBlackNumber(cur->_left,count,b_c)&&
                CheckBlackNumber(cur->_right,count,b_c);
    }


public:

    bool Role()
    {
        //根节点必须是黑的
        int decide=0;
        if(_root->_col==RED)
        {
            cout<<"规则二不满足"<<endl;
            decide++;
        }

        //没有连续的红节点
        if(!Continuation(_root))
        {
            cout<<"规则三不满足"<<endl;
            decide++;
        }

        //每个路径上的黑色节点都相同
        int black_count=0,count=0;
        Node *cur=_root;
        while(cur)
        {
            if(cur->_col==BLACK)
            {
                black_count++;
            }
            cur=cur->_left;
        }

        if( !CheckBlackNumber(_root,count,black_count))
        {
            cout<<"规则四不满足"<<endl;
            decide++;
        }
        return !decide;
    }



    bool insert(const pair<K,V>& kv)
    {
            //空节点的时候
            if(_root==nullptr)
            {
                _root= new Node(kv);
                _root->_col=BLACK;
                return true;
            }


            //插入
            Node *parent=nullptr;
            Node *cur=_root;
            while(cur)
            {
                if(cur->_val.first > kv.first)
                {
                    parent=cur;
                    cur=cur->_left;
                }
                else if(cur->_val.first < kv.first)
                {
                    parent=cur;
                    cur=cur->_right;
                }
                else
                {
                    return false;
                }
            }

            Node * present=new Node(kv);
            if(parent->_val.first > kv.first)
            {
                present->_parent=parent;
                parent->_left=present;
            }
            else
            {
                present->_parent=parent;
                parent->_right=present;
            }

            //更新红黑节点
            while(parent && parent->_col==RED)
            {
                Node * grandfather=parent->_parent;//祖父
                if(grandfather->_left==parent)
                {
                    Node* uncle = grandfather->_right;//叔叔

                    if(uncle != nullptr&&uncle->_col==RED)//情况1，叔叔为红色
                    {
                        uncle->_col=parent->_col=BLACK;
                        grandfather->_col=RED;

                        present=grandfather;
                        parent=present->_parent;
                    }
                    else//叔叔黑色，叔叔为空
                    {
                        if(present==parent->_left)//单旋
                        {
                            RotateR(grandfather);
                            parent->_col=BLACK;
                            grandfather->_col=RED;
                        }
                        else//双旋
                        {
                            RotateL(parent);
                            RotateR(grandfather);
                            parent->_col=grandfather->_col=RED;
                            present->_col=BLACK;
                        }
                        break;
                    }
                }
                else
                {
                    Node* uncle = grandfather->_left;
                    if(uncle != nullptr && uncle->_col==RED)//情况1，叔叔为红色
                    {
                        uncle->_col=parent->_col=BLACK;
                        grandfather->_col=RED;

                        present=grandfather;
                        parent=present->_parent;
                    }
                    else//情况2，叔叔为黑色或者不存在
                    {
                        if(present==parent->_right)//单旋
                        {
                            RotateL(grandfather);
                            parent->_col=BLACK;
                            grandfather->_col=RED;
                        }
                        else//双旋
                        {
                            RotateR(parent);
                            RotateL(grandfather);
                            parent->_col=grandfather->_col=RED;
                            present->_col=BLACK;
                        }
                        break;
                    }
                }
            }
        _root->_col=BLACK;
        return true;
    }
private:
    Node* _root=nullptr;
};

